A hash table or a hash map is a data structure that associates a given “key” with a given “value”. Hash tables are used for storing and accessing data in computer systems. Efficient storage and fast location of data are important features of a computer system and therefore improving hash table performance is an important consideration. Hash tables are used in many different applications within a computer system.
The primary operation of a hash table is a lookup: given a key (for example, a name), find the corresponding value (for example, a birth date). The hash table works by transforming the key using a hash function into a “hashcode” which is a number that is used as an index in an array to locate the desired location (a “bucket”) where the values should be.
To facilitate fast storage and retrieval, hash tables compute hashcodes of the keys. The hashcode is an identifier that is required to be identical for all keys that are considered equal within the data structure; however, some keys that are not equal may also have the same hashcode.
When storing or retrieving keys, known hash table implementations first look for those keys whose hashcodes are equal (a fast check) then test the keys themselves to determine if they are actually equal. The effect of only testing keys whose hashcodes are equal reduces the number of more time-costly key equality checks that must be performed.
Key equality checks are costly because they involve de-referencing object memory references for the keys being compared, which can cause central processing unit cache misses and thereby increased execution time to recover.
Known existing implementations of hash tables are not optimized for particular key types, so they suffer the drawback of having to support all possible key types.
It is an aim of the present disclosure to distinguish between different types of keys and use this knowledge to improve the data structure's overall performance.